package org.example.asm.sort;

import java.util.Scanner;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class SortTestTemplate01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //先读取数量数组的大小
        int n = in.nextInt();
        int[] nums = new int[n];
        int index = 0;
        while (in.hasNextInt()){
            nums[index] = in.nextInt();
            index ++;
        }
        //归并排序
        // mergeSort(nums);
        //快速排序
//        quickSort(nums, 0,  n - 1);
        //

        printRes(nums);
    }
    // 结果输出
    public static void printRes(int[] arr){
        for(int x : arr){
            System.out.print(x + " ");
        }
    }

    // 快速排序
    public static void quickSort(int[] arr, int low, int high){
        // 递归终止条件：当子数组长度小于等于1时
        if(low < high){
            //找到分段点
            int partition = partition(arr, low, high);
            //进行数组的左半部分排序
            quickSort(arr, low, partition - 1);
            //进行数组右半部分排序
            quickSort(arr, partition + 1, high);
        }
    }
    public static int partition(int[] arr, int low, int high){
        int shaobing = arr[high];
        int j = (low - 1);
        for (int i = low; i < high; i++) {
            if(arr[i] <= shaobing){
                j ++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[high] = arr[j + 1];
        arr[j + 1] = shaobing;
        return j + 1;
    }
    // ———————— 快速排序 ————————

    // 归并排序
    public static void mergeSort(int[] arr){
        //先进行校验
        if(arr == null || arr.length <= 1){
            return;
        }
        //先将原数组分成两半再进行合并排序操作
        int mid = arr.length / 2;

        int[] left = Arrays.copyOfRange(arr, 0, mid);
        mergeSort(left);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        mergeSort(right);

        //合并操作
        merge(arr, left, right);
    }

    // 合并两个已排序的数组到结果数组中
    public static void merge(int[] result, int[] left, int[] right) {
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                result[k++] = left[i++];
            }
            else{
                result[k++] = right[j++];
            }
        }
        //排序完后再进行判断
        while(i < left.length){
            result[k++] = left[i++];
        }
        while(j < right.length){
            result[k++] = right[j++];
        }

    }
    //———————— 归并排序 ——————————
}
